⭐️ 9.9. Dynamic Memory Allocation

32bit word (4 byte)를 기준으로 챕터가 진행된다. double word로 정렬한다는 것은 곧 모든 객체의 주소가 8의 배수가 된다는 것을 의미한다.

동적 메모리 할당자(dynamic memory allocator)로 힙 영역의 메모리를 어떻게 하면 편하게 할당하고 해제할 수 있을지에 대한 고민이 malloc의 구현에 영향을 주었다. 동적 메모리 할당 덕분에 우리는 mmap과 같은 낮은 수준의 메모리 관리로부터 벗어나게 되었다.

DUMP

Explicit Allocator & Implicit Allocator
- 명시적으로 할당/해제를 하는 C/C++는 Explicit Allocator이고 가비지 컬렉터가 참조 해제된 객체를 소거하는 자바는 Implicit Allocator이다.

9.9.1. The `malloc` and `free` functions

malloc(size)
free(ptr)
sbrk(incr)
free로 빈 공간을 다시 채우는 작업에 대한 도식

9.9.2. Why Dynamic Memory Allocation?

하드코딩된 전역배열을 프로덕션에서 사용하는 것은 미친 짓이기 때문.

9.9.3. Allocator Requirenments and Goals

Allocator의 제약조건

Handling arbitrary request sequences 할당과 해제가 꼭 대칭적으로만 이루어질 거라는 보장은 버려라.
Making immediate responses to requests 요청 즉시 메모리 공간을 반환
Using only the heap
Aligning blocks (alignment requirement)
Not modifying allocated blocks

Allocator의 달성수준

Maximizing throughput 임의의 요청에 빠르게 응답할 것
Maximizing Memory Utilization 현재 힙의 크기 대비 할당받은 블럭의 총량의 비율을 높일 것 (구멍의 수를 줄여라)

9.9.4. Fragmentation

Throughput에만 신경을 쓴다면 사실 free한 공간을 다시 재활용 하지 않아도 된다. 이 경우 두 가지 파편화가 발생할 수 있다.

Internal Fragmentation payload(실제로 필요한 용량)보다 할당해준 용량이 더 많은 경우, "고봉밥 할머니 style"
External Fragmentation 구멍의 총합은 큰데 너무 자잘해서 요청을 받아줄 수 없는 경우 → 휴리스틱 기법을 사용해 external frag를 줄이려고 노력한다. 어떻게? 작은 구멍의 크기보다는 큰 구멍의 크기를 유지하는 방향으로

9.9.5. Implementation Issues

결국 throughput과 mem utilization 모두 챙겨야 하는데, 참고할 만한 기준이 있을까?

Free block organization 구멍을 어떻게 추적하지?
Placement 할당요청에 어떤 구멍을 선택하지?
Splitting 할당에 구멍을 메웠다면, 남은 작은 구멍은 어떻게 관리하지?
Coalescing 방금 해제한 메모리 블럭을 어떻게 처리하지?

9.9.6. Implicit Free Lists

블럭의 첫번째 워드(head)(4byte)에 블럭에 대한 메타데이터를 저장한다. 별 건 아니고 블럭의 사이즈 (payload + padding)와 할당여부에 대한 정보를 담는다.

두 필드를 하나의 워드에 담을 수 있는게, 블럭 사이즈는 정렬 때문에 항상 8의 배수이기 때문이다. 따라서 앞의 3자리는 언제나 0인데, 0번째 비트 (LSB)를 0으로 만들면 Free, 1로 만들면 Allocated로 정의한다.

모든 블럭에는 헤더가 있으니까 헤더 정보를 보고 모든 블럭을 순회할 수 있긴 함. while (*cur & ~7) { cur += sizeof(void *) * (*cur & ~7); } 루프를 돌면서 계속 다음 블럭의 크기와 할당여부를 찾다가 block size == 0인 순간 힙 영역의 끝에 도달한거임.

헤더 때문에 최소 블럭 사이즈가 2 워드(8bytes) 가 된다.하나는 헤더, 다른 하나는 정렬 조건을 달성하기 위해서.

9.9.7. Placing Allocated Blocks

First Fit 걍 처음 길이가 맞는 구멍에 낑겨 들어가기
Next Fit 이전 검색이 중단된 지점에서부터 찾기
Best Fit 모든 구멍을 다 검사한 뒤 들어갈 수 있는 가장 작은 블럭을 찾아 들어간다. => 검색 속도를 빠르게 만든 Segregated Free List에 대해 알아볼 것이다!

9.9.8. Splitting Free Blocks

멍청하게 구멍 전체를 메우는 방식 -> internal fragmentation 발생
필요한 만큼만 구멍을 메우는 방식 -> 새롭고 더 작은 free block 탄생

9.9.9. Getting Additional Heap Memory

구멍이 서로 인접한 경우 -> coalescing (합체)
다 찾았는데도 알맞는 구멍이 없다면 -> sbrk 사용하여 커널에게 추가 힙 영역을 요구하는 수밖에

9.9.10. Coalescing Free Blocks

Immediate coalescing 즉각적인 병합은 간단하고 일정한 시간 내에 수행될 수 있지만, 일부 요청 패턴에서는 블록이 반복적으로 병합되었다가 곧 분할되는 형태의 스래싱이 발생할 수 있습니다.
defered coalescing 게으른 병합, 이번 장에서는 다루지 않는대.

9.9.11. Coalescing with Boundary Tags

footer의 도입으로 prev, post free blocks에 대한 병합이 상수 시간 안에 가능해졌다. 다만, 불필요한 메모리 오버헤드가 발생할 우려가 있다. 물론 이전 블럭이 해제되지 않은 경우라면 자기 블럭의 푸터를 사용하지 않는 방식으로 최적화를 도모할 수 있기는 하다. 아니면 아예 요청할 때 버퍼나 메모리 풀 따위를 두어서 큼직큼직하게 받던가

9.9.12. Putting It Together: Implementing a Simple Allocator

malloclab에서 진행한 실습 확인바람.

9.9.13. Explicit Free Lists

Implicit Free Lists 기법은 모든 블럭들을 순회하며 free block을 찾아야 해서 선형시간이 걸린다. 이 시간을 줄이기 위해 free block들의 페이로드 첫 두 바이트를 할애해 각각 predecessor와 successor를 두어 연결리스트로 만들어 버리는 방법이 있다.

하지만 결국 free block을 연결해봤자 선형시간인 건 똑같은데, 최적화 방법은 없을까?

Maintain the list in LIFO order by inserting newly freed blocks at the beginning of the list => 스택과 같은 순서로, 가장 최근에 free한 블럭먼저 본다.
Maintain the list in address order

9.9.14. Segregated Free Lists

concept

할당 시간을 줄이는 효과적인 방법으로 블록사이즈를 기준으로 같은 빈(또는 클래스)에 넣어버리는 방법을 분리가용리스트(segregated free list)라고 부른다. 대표적으로 블록사이즈를 2의 지수승에 따라 구분해 보관하게 되면 할당에 필요한 시간을 로그수준으로 줄일 수 있을 것이다.

Simple Segregated Free Lists

Free blocks are never split to satisfy allocatioin requests.

특이하게도, 블록을 쪼개지 않고 해당 빈에 있는 원소의 크기를 통째로 할당한다. => 내부 파편화가 심해질 수 있음.

빈에 원소가 없는 경우, OS에게 빈의 사이즈의 몇배 정도 되는 크기의 공간을 요청하여 빈을 채운 뒤 다시 할당한다. ==> coalesce가 없기 때문에 외부 파편화도 심해진다.

Segregated Fits

segregated free list이기는 한데, split과 coalescing이 가능한 케이스. free blocks를 사이즈에 따라 빈에 담는 건 똑같은데, 이제 새 블럭을 할당할 때 best fit 빈의 첫번째 요소를 찾아 split 후 할당한다. 남은 free block을 적절한 빈에 다시 추가한다.

블럭 해제시 근처 블럭을 병합한 뒤 적절한 빈에 다시 담는다.

Buddy Systems

빈의 크기가 2의 지수승인 Segregated Fits를 Buddy System이라고 부른다. 차이점이라면, Coalescing을 해제할 때가 아닌, 할당할 때 한다는 것이다.